package main

import (
	"fmt"
)

func main() {
	// s := "catsandog"
	// wordDict := []string{"cats", "dog", "sand", "and", "cat"}
	// s := "applepenapple"
	// wordDict := []string{"apple", "pen"}
	// s := "leetcode"
	// wordDict := []string{"leet", "code"}
	// s := "aaaaaaa"
	// wordDict := []string{"aaaa", "aaa"}
	// s := "abcd"
	// wordDict := []string{"a", "abc", "b", "cd"}
	s := "dogs"
	wordDict := []string{"dog", "s", "gs"}
	fmt.Println(wordBreak(s, wordDict))
}

// 递归处理，超时
func wordBreakrec(s string, wordDict []string) bool {
	if len(s) == 0 {
		return true
	}

	t := false
	for i := range s {
		for _, v := range wordDict {
			if s[:i+1] == v {
				t = true
				t = t && wordBreakrec(s[i+1:], wordDict)
				if t {
					return t
				}
			}
		}
	}

	return t
}

// dp[i] 保存第i个字符之前的字典满足
func wordBreak(s string, wordDict []string) bool {
	dp := make([]bool, len(s))
	for i := range s {
		for _, v := range wordDict {
			j := i - (len(v) - 1)
			if j >= 0 {
				if s[j:i+1] == v {
					if j == 0 {
						dp[i] = true
					} else {
						dp[i] = dp[j-1] && true
						if dp[i] {
							break
						}
					}
				}
			}
		}
	}

	return dp[len(s)-1]
}
